One of the elements within a computer operating system is memory management. Memory management consists of hardware and software that controls the allocation and use of physical memory. The effect of memory management is exemplified in multiprogramming systems in which several processes reside in memory at the same time. Memory management typically includes a virtual memory system. The virtual memory system provides the CPU (central processing unit) with mapping information. The CPU generates virtual addresses when an image is executed. Before these virtual addresses can be used to access instructions and data, they must be translated into physical addresses. Memory management software maintains tables of mapping information (page tables) that keep track of where each page of virtual addresses is located in physical memory. The CPU uses this mapping information when it translates virtual addresses to physical addresses. The mapping of virtual addresses through page tables in a virtual memory system provides a large virtual address space, and allows programs to run on hardware with smaller physical memory configurations.
The range of virtual addresses is referred to as the virtual address space. The virtual address space is that set of virtual addresses accessible by the current process. A process is current when its process context is loaded into the CPU and the process is actively executing. Only one process may be current on a given CPU at a given time. In existing systems, the virtual address space is divided into a shared address space, sometimes referred to as the system address space, and a per-process address space. The per-process address space is referred to as process private space. The shared address space maps code and data shared by all processes, and that is available to any process that is current. The shared address space may for example contain operating system code and data used by all processes. The process private space maps code and data associated with and available to one specific process only when that specific process is current. When the process context is changed, a new process is made current, and the mapping of process private space is changed to map process private space to process private code and data of that process.
A page table is typically used to map the virtual address space to physical memory, in units of "pages". A page is a multibyte unit of memory having a predetermined size. The specific size of a page varies from system to system. A page table contains page table entries (PTEs), each one of which defines a relationship (referred to as a "mapping") between a single virtual page and a physical page of memory. The physical address of a physical page of memory is referred to as a page frame number (PFN). Thus a given virtual page of memory is "mapped" to a page of physical memory by a specific PTE, and similarly that physical page of memory is "mapped" to the virtual page by that specific PTE. The PTE in that case is referred to as "mapping" the virtual page and the physical page of memory.
In existing computer systems, page table entries within a page table may be located in either process private or shared space. Where page table entries mapping process private space for a given process are located within process private space, the contents of those page table entries can ordinarily only be accessed when that specific process is current. Thus for a process to access the process private page table entries of another process, a context switch is typically required.
An operating system must at certain times make determinations regarding the relationship of a predetermined virtual address to the present process context. Certain aspects of the complexity of the current process context may impact the number and difficulty of determinations. For example, the memory management system must under certain circumstances clear the valid bit within a page table entry. As a result, the operating system must perform what is known as a "translation buffer invalidate" operation. Operating system software associated with that operation is caused to be executed. This software will be referred to as "translation invalidation" software. Such software must make a number of determinations regarding the page of virtual memory mapped by the page table entry in which the valid bit has been cleared. These determinations for example must be made in the context of a multiprocessor system in order to minimize the number of translation buffer invalidations performed across the total number of central processing units (CPUs) in the system.
For example, the software must determine:
(1) whether the virtual addresses mapped by the page table entry are within process private space or shared space, PA1 (2) whether the virtual addresses mapped by the page table entry are the virtual addresses of page table entries, and PA1 (3) if the virtual addresses mapped by the page table entry are the virtual addresses of page table entries, whether the virtual addresses are virtual addresses of page table entries mapping process private space or of page table entries mapping shared space.
In a first case the virtual addresses mapped by the page table entry are either within process private space, or are the virtual addresses mapping a page of page table entries mapping process private space. In this first case, relevant virtual address translations need to be invalidated locally. Specifically, translations of virtual addresses within the page of virtual addresses mapped by the page table entry need only be invalidated in (or "flushed" from) any translation buffer within the central processing unit (CPU) on which the operating system software is currently executing. That CPU is referred to herein for purposes of example as the "current" CPU.
In a second case, where it is determined that the virtual addresses mapped by the page table entry are not in process private space and is not a page of virtual addresses of process private page table entries, then the page of virtual addresses is shared by all processes in the system and those virtual address translations must be invalidated globally. Specifically, any translations of virtual addresses within the page of virtual addresses mapped by the page table entry need to be invalidated (or "flushed") from any translation buffer of each central processing unit (CPU) in the multiprocessor system.
In existing systems, page table entries mapping the private space of any given process, whether current or not, are mapped to an individual section of shared space associated with that process. Each such section is delimited by a top pointer and a bottom pointer. In such systems, operating system functions such as the translation invalidation software must potentially compare a virtual address (for example of the page mapped by the page table entry whose valid bit is cleared) with (1) a boundary dividing shared space from process private space, (2) a top pointer of the section of shared space mapping the page table entries mapping private space for the current process, and (3) a bottom pointer of the section of shared space mapping the page table entries mapping private space for the current process. Each of these comparisons occurs in performance critical software, and adversely impacts the overall system throughput and response time.
Further, in existing systems, address comparisons made by operating system processes such as the translation invalidation software are based on parameters specific to the currently running process, i.e. the top and bottom pointers for the section of shared space mapping the page table entries mapping private space for the current process. Such use of process specific parameters is costly and should be avoided to improve system performance.
The above limitations and drawbacks of current systems described for purposes of example with regard to translation invalidation apply to many other areas of the operating system. For further example, the operating system software responsible for handling a page fault, where reference is made to a virtual address that is mapped by a page table entry whose valid bit is not set, must make similar determinations as described above. As a result there is a detrimental impact on existing system performance in many areas of the operating system related to the virtual address design.
Accordingly there is required a new memory management system in which fewer address comparisons are needed to process such events as translation buffer invalidation and/or page faults. The new system should further advantageously reduce the amount of context specific information needed to process such events.